package com.tgy.map;


import com.tgy.util.printer.BinaryTreeInfo;
import com.tgy.util.printer.BinaryTrees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2020-09-27 14:48
 */
public class HashMap<K,V> implements Map<K,V> {



    private static enum RotateEnum{
        /**
         * 向左旋转
         */
        LEFT,
        /**
         * 向右旋转
         */
        RIGHT

    }

    private static enum Color{

        /**
         * 黑色节点
         */
        BLACK,
        /**
         * 红色节点
         */
        RED

    }

    private static class Node<K,V>{

        /**
         * 默认节点是红色
         */
        private Color color = Color.RED;

        int hash;
        K key;
        V value;

        Node<K, V> parent,left,right;

        public Node(K key, V value, Node<K, V> parent) {

            this.key = key;
            this.value = value;
            this.parent = parent;
            hash = Objects.hashCode(key);
        }


        /**
         * 获取当前节点的度
         * @return
         */
        public int degreed() {

            if (Objects.nonNull(left) && Objects.nonNull(right)) {

                return 2;
            }

            if (Objects.isNull(left) && Objects.isNull(right)) {

                return 0;
            }
            return 1;
        }

        public boolean isLeaf() {

            return Objects.isNull(left) && Objects.isNull(right);
        }

        /**
         * 当前节点是父节点的左节点
         * @return
         */
         boolean isLeftNode() {

            return parent !=null && this.equals(parent.left);
        }

        /**
         * 当前节点是父节点的右节点
         * @return
         */
         boolean isRightNode() {

            return parent != null && this.equals(parent.right);
        }

        /**
         * 判断当前节点是否是黑色节点
         * @return
         */
        public boolean isBlack() {

            return color == Color.BLACK;
        }

        /**
         * 判断当前节点是否是红色节点
         * @return
         */
        public boolean isRed() {

            return color == Color.RED;
        }

        /**
         * 把当前节点变成黑色
         * @return
         */
        public Node<K,V> black(){

            color = Color.BLACK;
            return this;
        }

        /**
         * 把当前节点变成红色
         * @return
         */
        public Node<K,V> red() {

            color = Color.RED;
            return this;
        }

        public Node<K,V> color(Color color) {

            this.color = color;
            return this;
        }

        /**
         * 获取父节点
         * @return
         */
        public Node<K,V> parent(){

            return (Node<K,V>) this.parent;
        }

        /**
         * 获取左节点
         * @return
         */
        public Node<K,V> leftNode() {

            return  this.left;
        }

        /**
         * 获取右节点
         * @return
         */
        public Node<K,V> rightNode() {

            return this.right;
        }



        /**
         * 获取当前节点的兄弟节点
         * @return
         */
        public Node<K,V> sibling() {

            if (parent == null) {

                return null;
            }

            if (isLeftNode()) {

                return parent().rightNode();
            }else if (isRightNode()) {

                return parent().leftNode();

            }
            return null;
        }

        /**
         * 获取父节点的兄弟节点
         * @return
         */
        public Node<K,V> uncle() {

            if (grand() == null) {

                return null;
            }

            if (parent().isLeftNode()) {

                return grand().rightNode();
            }else{

                return grand().leftNode();
            }
        }



        /**
         * 获取祖父节点(父节点的父节点)
         * @return
         */
        public Node<K,V> grand() {

            return parent() == null? null: parent().parent();
        }

        @Override
        public String toString() {

            return key + "_" + value  +":(" + color.name() + ")";
        }

        public static <K,V> boolean isBlack(Node<K,V> node) {

            if (node == null) {

                return true;
            }

            return node.isBlack();
        }
    }


    /**
     * 记录插入到hashmap的元素个数
     */
    int size;

    private static float LOADFACTOR = 0.75f;

    /**
     * 默认容量是 16
     */
    private static int INIT_CAPACITY = 2 << 4;

    Node<K,V>[] buckets;

    public HashMap() {

        this(INIT_CAPACITY);
    }

    public HashMap(int capacity) {

        if (capacity <= INIT_CAPACITY) {

            capacity = INIT_CAPACITY;
        }else {

            capacity = adjustCapacity(capacity);
        }

        buckets = new Node[capacity];
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {

        buckets = new Node[INIT_CAPACITY];
        size = 0;
    }

    @Override
    public V put(K key, V value) {

        // 调整buckets数组容量
        ensureContainer();

        int index = indexOfHash(key);

        Node<K, V> node = buckets[index];

        if (Objects.isNull(node)) {

            Node<K,V> newNode= new Node<K,V>(key,value,null);
            buckets[index] =  newNode;
            size++;

            addAdjustTree(newNode);
        }else {

            int compareResult;
            Node<K,V> beforeNode = null;

            int p;
            int keyHashCode = Objects.hashCode(key);
            boolean flag = true;
            do {

                beforeNode = node;

                if (node.hash > keyHashCode) {

                    compareResult = 1;
                }else if (node.hash < keyHashCode) {

                    compareResult = -1;
                }else if (Objects.equals(node.key,key)){

                    compareResult = 0;
                }else  if (Objects.nonNull(node.key) && Objects.nonNull(key) &&
                        (Objects.equals(node.key.getClass().getName(),key.getClass().getName())) &&
                        (node.key instanceof Comparable) &&
                        (compareResult = ((Comparable)node.key).compareTo(key))!= 0) {


                }else if (flag) {

                    if ((Objects.nonNull(node.right) && (Objects.nonNull(beforeNode = nodeOfKey(node.right,key)))) ||
                            (Objects.nonNull(node.left) && (Objects.nonNull(beforeNode = nodeOfKey(node.left,key))))) {

                        compareResult = 0;

                    }else {

                        beforeNode = node;
                        flag = false;
                        compareResult = System.identityHashCode(node.key) - System.identityHashCode(key);
                    }
                }else {

                    compareResult = System.identityHashCode(node.key) - System.identityHashCode(key);
                }


                if (compareResult > 0) {

                    node = node.left;
                }else if (compareResult < 0){

                    node = node.right;
                }else {

                    break;
                }

            }while (Objects.nonNull(node));


            Node<K, V> newNode = new Node<>(key, value, beforeNode);

            if (compareResult < 0) {

                beforeNode.right = newNode;
            }else if (compareResult > 0){

                beforeNode.left = newNode;
            }else {

                beforeNode.value = value;
                return value;
            }

            size++;
            addAdjustTree(newNode);
        }

        return null;
    }


    @Override
    public V get(K key) {

        Node<K, V> findNode = nodeOfKey(rootOfKey(key),key);
        return findNode == null? null:findNode.value;
    }

    @Override
    public V remove(K key) {


        int index = indexOfHash(key);
        Node<K, V> node = buckets[index];

        if (Objects.isNull(node)) {

            return null;
        }

        Node<K, V> removeNode = nodeOfKey(node,key);

        if (Objects.isNull(removeNode)) {
            return null;
        }

        V removeValue = removeNode.value;
        if (removeNode.degreed() == 2) {
//          如果度为2，则找到下一个后继节点，把后继节点度element值放到当前位置，删除后继节点
            Node<K,V> tmpNode = successor(removeNode);

            removeNode.key = tmpNode.key;
            removeNode.value = tmpNode.value;
            removeNode.hash = tmpNode.hash;
            removeNode = tmpNode;
        }

        if (removeNode.degreed() == 1) {
//            处理度为1的节点
            Node<K,V> replaceNode;
            if (Objects.nonNull(removeNode.parent)) {

                if (removeNode.isLeftNode()) {
                    removeNode.parent.left = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                    removeNode.parent.left.parent = removeNode.parent;

                    replaceNode = removeNode.parent.left;
                }else {

                    removeNode.parent.right = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                    removeNode.parent.right.parent = removeNode.parent;
                    replaceNode = removeNode.parent.right;
                }

            }else {

                buckets[index] = Objects.isNull(removeNode.left)?removeNode.right:removeNode.left;
                buckets[index].parent = null;

                replaceNode = buckets[index];
            }

            removeAdjustTree(replaceNode);

        }else {
//            处理度为0的节点
            if (Objects.nonNull(removeNode.parent)) {

                if (removeNode.isLeftNode()) {

                    removeNode.parent.left = null;
                }else {

                    removeNode.parent.right = null;
                }

                removeAdjustTree(removeNode);

            }else {
                buckets[index] = null;
            }
        }

        size--;

        return removeValue;
    }

    @Override
    public boolean containsKey(K key) {

        return Objects.nonNull(nodeOfKey(rootOfKey(key),key));
    }

    @Override
    public boolean containsValue(V value) {

        if (isEmpty()) {

            return false;
        }

        LinkedList<Node<K, V>> queue = new LinkedList<>();
        Node<K,V> node;

        for (Node<K, V> bucket : buckets) {

            if (Objects.isNull(bucket)) {
                continue;
            }

            queue.offer(bucket);

            do {

                node = queue.poll();
                if (Objects.equals(node.value,value)) {

                    return true;
                }

                if (Objects.nonNull(node.left)) {

                    queue.offer(node.left);
                }

                if (Objects.nonNull(node.right)) {

                    queue.offer(node.right);
                }

            }while (!queue.isEmpty());

        }

        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {

        if (isEmpty() || Objects.isNull(visitor)) {

            return;
        }

        Stack<Node<K, V>> stack = new Stack<>();
        Node<K,V> node;
        for (Node<K, V> bucket : buckets) {

            if (Objects.isNull(bucket)) {
                continue;
            }

            node = bucket;

            do {

                while (Objects.nonNull(node)) {

                    stack.push(node);
                    node = node.left;
                }

                node = stack.pop();
                if (visitor.visit(node.key,node.value)) {

                    return;
                }

                node = node.right;

            }while (Objects.nonNull(node) || !stack.isEmpty());
        }
    }

    /**
     * 打印hashmap内部的每一个bucket
     */
    public void print() {

        for (int i = 0; i < buckets.length; i++) {

            final Node<K,V> node = buckets[i];
            if (Objects.isNull(node)) {

                continue;
            }

            BinaryTreeInfo binaryTreeInfo = new BinaryTreeInfo() {

                @Override
                public Object root() {
                    return node;
                }

                @Override
                public Object left(Object node) {

                    return ((Node<K, V>) node).left;
                }

                @Override
                public Object right(Object node) {

                    return ((Node<K, V>) node).right;
                }

                @Override
                public Object string(Object node) {

                    return node;
                }
            };

            BinaryTrees.println(binaryTreeInfo);
            System.out.println("------");
        }

    }

    private Node<K,V> nodeOfKey(Node<K,V> node,K key) {


        if (Objects.isNull(node)) {
            return null;
        }

        int p;
        int keyHashCode = Objects.hashCode(key);
        Node<K,V> resultNode;
        do {

            if (node.hash > keyHashCode) {

                node = node.left;
            }else if (node.hash < keyHashCode) {

                node = node.right;
            }else if (Objects.equals(node.key,key)){

                return node;
            }else  if (Objects.nonNull(node.key) && Objects.nonNull(key) &&
                        (Objects.equals(node.key.getClass(),key.getClass())) &&
                        (node.key instanceof Comparable) &&
                    (p = ((Comparable)node.key).compareTo(key))!= 0) {

                if (p > 0) {

                    node = node.left;
                }else {

                    node = node.right;
                }

            }else if (Objects.nonNull(node.right) && (Objects.nonNull(resultNode = nodeOfKey(node.right,key)))) {

                return resultNode;
            }else {

                node = node.left;
            }

        }while (Objects.nonNull(node));

        return null;
    }

    private Node<K,V> rootOfKey(K key) {

        int index = indexOfHash(key);
        Node<K, V> node = buckets[index];
        return node;
    }

    /**
     * 获取key的hash值
     * @param key
     * @return
     */
    private int indexOfHash(K key) {

        return doIndexOfHash(Objects.hashCode(key),buckets.length);
    }

    private int doIndexOfHash(int hashCode,int length) {

        return (hashCode ^ (hashCode>>>16)) & (length - 1);
    }

    /**
     * 确保buckets数组容量
     */
    private void ensureContainer() {

        if (size < buckets.length * LOADFACTOR) {

            return;
        }

        Node[] newbuckets = new Node[buckets.length << 1];

        LinkedList<Node> queue = new LinkedList<>();
        for (Node<K, V> bucket : buckets) {


            if (Objects.isNull(bucket)) {
                continue;
            }

            queue.offer(bucket);

            while (!queue.isEmpty()) {

                Node node = queue.poll();

                if (Objects.nonNull(node.left)) {

                    queue.offer(node.left);
                }

                if (Objects.nonNull(node.right)) {

                    queue.offer(node.right);
                }

                // 处理node
                putNewNode(newbuckets,node);
            }
        }

        buckets = newbuckets;

    }

    private void putNewNode(Node<K,V>[] newbuckets, Node<K,V> insertNode) {

        // 初始化node
        insertNode.left = null;
        insertNode.right = null;
        insertNode.color = Color.RED;


        int index = doIndexOfHash(insertNode.hash,newbuckets.length);
        Node node = newbuckets[index];

        if (Objects.isNull(node)) {

            newbuckets[index] = insertNode;
            insertNode.parent = null;
            addAdjustTree(insertNode);
        }else {

            int compareResult;
            Node<K,V> beforeNode = null;
            do {
//                System.out.println("11" + node.key + " === " + insertNode.key + " size = " + buckets.length);
                beforeNode = node;
                if (node.hash > insertNode.hash) {

                    compareResult = 1;
                }else if (node.hash < insertNode.hash) {

                    compareResult = -1;
                }else  if (Objects.nonNull(node.key) && Objects.nonNull(insertNode.key) &&
                        (Objects.equals(node.key.getClass().getName(),insertNode.key.getClass().getName())) &&
                        (node.key instanceof Comparable)) {

                    compareResult = ((Comparable)node.key).compareTo(insertNode.key);

                }else {

                    compareResult = System.identityHashCode(node.key) - System.identityHashCode(insertNode.key);
                }

                if (compareResult > 0) {

                    node = node.left;
                }else if (compareResult < 0){

                    node = node.right;
                }

            }while (Objects.nonNull(node));

            if (compareResult < 0) {

                beforeNode.right = insertNode;
            }else if (compareResult > 0){
                beforeNode.left = insertNode;
            }

            insertNode.parent = beforeNode;
            addAdjustTree(insertNode);
        }
    }

    /**
     * 调整capacity为 2^n
     * @param capacity
     * @return
     */
    private int adjustCapacity(int capacity) {

        int times = 0;

        do {
            capacity = capacity >> 1;
            times++;
        }while (capacity != 0);

        return (int) Math.pow(2,times);
    }


    private void addAdjustTree(Node<K,V> node) {


        /**
         * 根节点
         */
        if (Objects.isNull(node.parent) ) {

            node.black();
            return;
        }

        /**
         * 如果添加节点的父节点是黑色，则直接添加，什么都不做
         */
        if (node.parent().isBlack()) {

            return;
        }

        if (Node.isBlack(node.uncle())) {

            Node<K,V> grand = node.grand();
            Node<K,V> parent = node.parent();
            // 如果uncle 为黑色,旋转
            if (parent.isLeftNode()) {

//                L
                if (node.isLeftNode()) {

//                    L
                    parent.black();
                }else {
//                    R
                    rotate(parent,RotateEnum.LEFT);
//                    rotate(grand,RotateEnum.RIGHT);
                    node.black();
                }
                rotate(grand,RotateEnum.RIGHT);

            }else {

//                R
                if (node.isLeftNode()) {
//                    L
                    rotate(parent,RotateEnum.RIGHT);
                    node.black();
                }else {
//                    R
//                    rotate(grand,RotateEnum.LEFT);
                    parent.black();
                }
                rotate(grand,RotateEnum.LEFT);
            }

            grand.red();
        }else {

            // 拆分B树节点
            node.uncle().black();
            node.grand().red();
            node.parent().black();
            addAdjustTree(node.grand());
        }
    }

    private void removeAdjustTree(Node<K,V> node) {

        if (node.isRed() || node.parent == null) {

            node.black();
            return;
        }

        Node<K,V> parentNode = node.parent();

        /**
         *      由于在BinarySearchTree 中如果是左树，则把父节点的left置为null 判断是左树还是右树
         *      1. parentNode.leftNode() == null
         *          从父类进入本方法
         *      2. node.isLeftNode()
         *         模拟父节点删除进入本方法
         *
         */
        boolean isLeft = (parentNode.leftNode() == null) || node.isLeftNode();

        if (isLeft) {
            // 判断兄弟节点是否是black
            Node<K,V> sibling = parentNode.rightNode();
            if (sibling.isRed()) {

                rotate(node.parent,RotateEnum.LEFT);
                sibling.black();
                parentNode.red();
                sibling = parentNode.rightNode();
            }

            if (Node.isBlack(sibling.leftNode())  && Node.isBlack(sibling.rightNode())) {

                // 兄弟节点染成红色
                sibling.red();
                // 没有红色的子节点
                if (parentNode.isRed()) {
//                      父节点是红色,直接把父节点染成黑色
                    parentNode.black();
                }else {
//                     相当于删除父节点,重新走一遍调整逻辑
                    removeAdjustTree(parentNode);
                }
            }else {

                // 如果兄弟节点的右节点是黑色，则左节点一定是红色，则进行右旋转
                if (Node.isBlack(sibling.rightNode())) {

                    rotate(sibling,RotateEnum.RIGHT);
                    sibling.red();
                    sibling =parentNode.rightNode();
                }

                sibling.color(parentNode.color);
                parentNode.black();
                if (sibling.rightNode() != null) {

                    sibling.rightNode().black();
                }
                rotate(node.parent(),RotateEnum.LEFT);
            }

        }else {
            // 判断兄弟节点是否是black
            Node<K,V> sibling = parentNode.leftNode();
            if (sibling.isRed()) {

                rotate(node.parent,RotateEnum.RIGHT);
                sibling.black();
                parentNode.red();
                sibling = parentNode.leftNode();

            }

            if (Node.isBlack(sibling.leftNode())  && Node.isBlack(sibling.rightNode())) {

                // 兄弟节点染成红色
                sibling.red();
                // 没有红色的子节点
                if (parentNode.isRed()) {
//                      父节点是红色,直接把父节点染成黑色
                    parentNode.black();
                }else {
//                     相当于删除父节点,重新走一遍调整逻辑
                    removeAdjustTree(parentNode);
                }
            }else {

                // 如果兄弟节点的左字节是黑色，则右节点一定是红色，则进行左旋转
                if (Node.isBlack(sibling.leftNode())) {

                    rotate(sibling,RotateEnum.LEFT);
                    sibling.red();
                    sibling = parentNode.leftNode();
                }

                sibling.color(parentNode.color);
                parentNode.black();
                if (sibling.leftNode() != null) {

                    sibling.leftNode().black();
                }
                rotate(node.parent(),RotateEnum.RIGHT);
            }
        }

    }

    private void rotate(Node<K,V> gNode, RotateEnum rotateEnum){

        Node<K,V> pNode;

        if (rotateEnum == RotateEnum.LEFT) {

            pNode = gNode.right;
        }else {

            pNode = gNode.left;
        }

        if (gNode.parent == null) {

            buckets[indexOfHash(pNode.key)] = pNode;
        }else {

            if (gNode.isLeftNode()){

                gNode.parent.left = pNode;
            }else {

                gNode.parent.right = pNode;
            }
        }

        pNode.parent = gNode.parent;
        gNode.parent = pNode;

        if (rotateEnum == RotateEnum.LEFT) {

            if (pNode.left != null) {

                pNode.left.parent = gNode;
            }
            gNode.right = pNode.left;
            pNode.left = gNode;

        }else {

            if (pNode.right != null) {

                pNode.right.parent = gNode;
            }
            gNode.left = pNode.right;
            pNode.right = gNode;
        }
    }

    private Node<K,V> successor(Node<K,V> node) {

        if (Objects.isNull(node)) {
            return null;
        }

        if (Objects.nonNull(node.right)) {

            node = node.right;
            while (Objects.nonNull(node.left)) {

                node = node.left;
            }

            return node;

        }else {

            while (Objects.nonNull(node.parent)) {

                if (Objects.equals(node.parent.left,node)) {
                    return node.parent;
                }
                node = node.parent;
            }
        }

        return null;
    }
}
